COMPUTER VISION
				by
		 Thomas O. Binford, Stanford University 
				and
		Jay M. Tenenbaum, Stanford Research Institute


			Introduction.

Intelligent computers require knowledge of their environment, and the
most effective means of acquiring such knowledge is by seeing. Vision
opens  a  new  realm  of computer applications. Weather analysis from
cloud maps and medical diagnosis from x-rays and  blood  cell  counts
are  two  of  many  high  volume  data  processing tasks that require
pictorial input.  Man-machine communication will be facilitated if  a
person  can  directly  show  the  computer a real object, rather than
having to describe it symbolically.  Designers,  for  example,  could
then  easily  obtain  a  computerized  structural  analysis  of scale
models.

A particularly exciting area of application is industrial automation.
Today  in  industry  there are hundreds of machines called industrial
robots.   These programmable manipulators can repetitively execute  a
precise  sequence  of motions but have no sensors and are thus unable
to  react  dynamically  to  contingencies.    Simple  sensors  and  a
minicomputer   could,   at   slight   additional   cost,  turn  these
manipulators into true robots. With primitive visual  skills,machines
could align mating parts in assembly operations, increase reliability
by self-calibration, detect flaws and avoid  disasters.  Vision  will
also  minimize  the  present need for precise positioning of parts at
each work station; parts could instead be transported in  a  bin  and
picked out as needed.

The  study  of  perception also provides valuable insights into human
and machine information processing. Many of the problems  encountered
are  widespread in intelligence: How is knowledge represented?    How
does it guide in drawing conclusions from perceptual data?  How  does
existing  knowledge  interact with conclusions drawn from an image to
acheive learning?  Issues that arise in the implementation of  vision
systems  have  broad  relevance  to  computer science:   How shoulc a
complex task be partitioned into  modules?  How  should  the  modules
communicate  to share their knowledge and special capabilities?   How
should systems with highly interdependent modules  be  structured  to
facilitate modification?

Techniques developed for machine perception cannot be taken literally
as models for biological systems because of differences  in  hardware
and  gaps  in  our knowledge.    However, fundamental limitations are
shared, suggesting that some of the principles might also be found in
nature.  The research may, in turn, occasionally borrow from biology,
but we cannot copy nature, since again, the details are not yet known
and the hardware is different.


Historically,  computer  vision  emerged  from  the  study   of   two
dimensional  pattern  recognition.  However, it is seldom possible to
apply the mathematical formalisms developed for classification to the
analysis  of  real  scenes.  Consider  the visual requirements for an
organism such as a robot. It must manipulate or  avoid  objects,  not
just  classify  them.        Manipulation  requires three-dimensional
interpretations and spatial relations of objects.  In  problems  like
character  recognition,  it  was  attractive to simply save images or
feature vectors, then match against an image or part of an image. But
in  real  scenes,  objects  occlude one another, they have parts with
joints that move separately, there are many viewpoints, many possible
objects,  and many combinations of objects. Object classes, moreover,
are often defined by function, not shape (eg.  the  class  of  coffee
cups).    Direct  template  matching  techniques  are impractical for
these requirements, except in very carefully controlled applications.
Perception  involves  complex  deductions  to  understand an image in
terms of a priori knowledge of the world.
	ELEMENTS OF A VISUAL SYSTEM

The  computer  eye is some form of tv camera with color filters and a
turret or zoom lens  for  closeup  views.     The  computer  controls
filters,  lens  and  other  parameters to optimize the image for each
task [Tenenbaum 1970].   A recent  study  has  suggested  alternative
sensors  to  overcome  the  inadequate  dynamic  range  of television
systems [Binford 1972].  Range  information  greatly  simplifies  the
interpretation  of scenes. Humans use depth information obtained from
stereo and a variety of inferred cues such as motion parallax and the
size  of  known  objects.  Since  these techniques require subtantial
processing, it is easier for  machines  to  obtain  depth  by  direct
measurement.  Several  depth sensors based on triangulation have been
built [Agin 1972, Shirai 1972a].

An image is read  into  memory  as  an  array  of  brightness  values
(typically 300x300) with 4-8 bits for each sample for each color. The
process  of  interpreting  this  mass  of  numbers  into  a  symbolic
description  can  be  thought  of  as  subdivided  into segmentation,
representation, and interpretation.

The process  of  segmentation  partitions  a  scene  into  meaningful
entities  which  may  be recognizable.      Segmentation in character
recognition  is  simple  since  printed  characters   are   spatially
separated  and  have  high contrast with white paper. It is harder to
segment objects in a real scene (even simple  scenes)  since  objects
may  overlap  and  will  not  usually  be  separable  from  the local
background by a single attribute like brightness  contrast.  Instead,
segmentation  must  proceed by seeking regions of uniform brightness,
color, or texture (itself a  complex  descriptor),  or  regions  with
regular  boundaries.  Segmentation  may also depend on inferred depth
cues (e.g., texture gradients or suspected occlusion).

In what form can we represent objects internally in the computer? The
simplest  form is a pictorial template, an array of brightness values
to be matched directly against fragments of  scenes  by  correlation.
Given  the  inadequacies  of  this  representation,  we must describe
partitioned regions symbolically in terms of extracted features  like
color,  size,  texture, and shape.  All these properties are inferred
by complex processes from the image.  Simple descriptors for shape or
texture  may be used in simple tasks and limited context. Shape might
be described by the ratio of the squared perimeter to the area  of  a
region.  More sophisticated shape representations, needed for a wider
range of tasks, are described later.

Interpretation is often expressed as  computing  a  distance  measure
between  an  object and a stored model.  For simple cases that can be
useful.     When objects are occluded, there must be a partial match.
When  objects  are  not  identical, judgments of similarity depend on
representation of shape and representation of the task, in  order  to
define  important  differences.  The most useful approach is to build
up  symbolic  descriptions  and   make   symbolic   descriptions   of
differences.    Sometimes,  there are few enough models that matching
with each model is possible. More generally,  the  observed  features
must  first  be  used  to  retrieve likely models from a large visual
memory.

The integration of segmentation, representation and interpretation to
achieve perception is illustrated by a system built at the University
of Edinburgh [Barrow  1971]  which  can  recognize  a  small  set  of
ordinary  objects such as pencils, eye-glasses and teacups.   Objects
are presented  against  a  contrasting  background.  Segmentation  is
achieved   by   partitioning   the  scene  into  regions  of  uniform
brightness. Objects are represented by  relational  graphs  detailing
gross attributes (size, shape) of their principle regions and spatial
constraints  between  them.     Interpretation  is  accomplished   by
mapping  the  relational graph descriptions of known objects onto the
segmented regions obtained from the scene and seeking the best match.

Experience with early bottom-up systems  of  this  type  led  to  the
realization  that  the  three  basic processes of a perceptual system
were highly interdependent; one cannot proceed  sequentially  through
segmentation,  representation and interpretation and expect to obtain
a globally consistent interpretation for all objects in a scene.  One
problem  is  that  no  reliable  basis  exists for judging the global
significance  of  segmentation  boundaries  using  local   similarity
criteria.  Segmentation  must  be  guided by interpretation to choose
among many alternative partitionings, that which leads to a  globally
consistent and reasonable description of the scene. A nice exposition
of these ideas is given by Minskey [1972].

		BLOCKS WORLD

To avoid some of these difficulties, research concentrated  initially
on  scenes  of toy blocks.  Roberts' [1963] important work opened the
field [].  Objects were represented as built up  of  three  primitive
parts,  a  block, a wedge, and a hexagonal prism. The program assumed
it would first obtain perfect  line  drawings.  Interpretation  meant
choosing  a  stored  three-dimensional model which after translation,
rotation and scaling could be projected to match part of  the  image.
The  recognized piece was then cut away and the remainder considered.
Primitives were represented by their vertices in three dimensions. To
decide  on  likely  image points which belonged to a single body, the
program attempted to identify unobscured polygons, then match sets of
vertices  to topologically similar model vertices. Line drawings were
formed by a sequence of local operations.  Candidate edge points were
considered  by thresholding the gradient of intensity.  Isolated edge
points were discarded.   Connected line fragments  were  concatenated
into  lines  which  were  segmented  at corners by a sequential least
squares line fit.  Merging of colinear lines bridged some gaps.

That system organization has proven inadequate. It is not  enough  to
use  models and template matching. Producing perfect line drawings is
not practical:    some lines are  missed;  shadows,  reflections  and
surface  markings  cause  extra  lines;  errors made at one stage are
compounded by later stages.  These deficiencies motivated  subsequent
research.

Guzman  [1968]  found  it  possible  to  segment  complex scenes into
objects without template matching, by observing  that  some  vertices
give local evidence that adjacent regions belong to the same body. In
figure 1, vertices  A,B,C,E,G  and  H  give  evidence  that  adjacent
regions  belong  to the same body, while vertex F does not.  Vertex D
which  resembles  G  gives  misleading  evidence.   To   avoid   such
coincidences,  the program required confirmation.      Regions linked
twice were joined into clusters; regions linked twice  to  a  cluster
were  also  joined. Regions linked only to a single cluster were also
joined to that cluster. Eventually, the program  evolved  to  include
inhibitions  against certain links by requiring similar conditions at
both ends of  a  line.  Other  links  were  introduced  without  much
motivation.

This  program  was an important advance.    Bodies could be segmented
without recognition and without explicit models.    The  program  did
surprisingly   well,   but   had   problems   with  holes  and  other
non-convexities, and with  accidental  alignment.    being  told  the
background.    Guzman  also  could  not cope well with imperfect line
drawings. His program would fail figure  2  because  a  missing  line
makes  region  R3 common to both the block and wedge. Falk [1972] was
able to avoid some of the errors associated with  missing  boundaries
by  using  a  Guzman  like  approach  to link line segments likely to
belong to the same object instead of regions.

The limited generality of both these programs was  due  to  the  fact
that  they  were  implemented as a collection of adhoc heuristics for
segmentation with no explicit understanding of line drawings.   Thus,
while  Falk himself realized that regions like R3 were non-planer and
could not arise in a scene  containing  only  trihedral  solids,  his
program  could  not  reason  at this level. Huffman [1971] and Clowes
[1971] made theoretical  analyses  of  objects  with  only  trihedral
vertices (three planes at each vertex).  By classifying edges at each
vertex as convex, concave  and  obscuring,  they  could  reject  some
drawings  as  impossible if a given line was not consistently labeled
at each end. Waltz [1972] expanded that labelling of lines to include
cracks  and  whether  adjacent  regions were shadowed or illuminated.
Since each vertex could have many interpretations. it would seem that
a search for consistent labelings would be unmanageable.     Instead,
the increased precision of descriptions allows  rapid  discarding  of
wrong  interpretations.     Not only are solutions possible, they are
quickly obtained. Instead of a complete tree search, it was  adequate
to   consider   vertices   in   sequence,   eliminating  inconsistent
interpretations as each new vertex was  added.    This  produced  all
possible  interpretations  of a scene. However, some evaluations were
possible  to  choose  reasonable  interpretations,  in   cases   with
ambiguous  interpretations.   A  detailed  survey of the work through
Huffman appears in a recent text by Duda and Hart [1972].





The best performance in  extracting  line  drawings  from  television
images   of  polyhedra  is  given  by  the  Shirai  [1972b]  and  the
Binford-Horn [Horn 1971]  line  finders.   Shirai's  system  performs
better,  but  requires  large contrast between objects and background
(e.g., white on black), and finds only features and objects for which
cues  are available from context.     The Binford-Horn system is able
to find most lines in a scene of white blocks on a  white  background
in  arbitrary  lighting.  It  misses a few lines which can usually be
inferred from those that  were  found,  and  garbles  some  vertices.
The two are complementary and should be combined.

The two programs are based on different principles.  Shirai's program
first found the outer boundaries of an object or cluster of  objects.
It  then  tried  to  guess  additional  lines  which  were  parallel,
perpendicular or extensions  to  lines  already  found.   Search  for
missing lines concentrated around vertices in the preliminary drawing
where they would be most likely found. The use  of  context  involved
not changing thresholds, but using special-purpose operators:  verify
a line at known position and angle; find a  line  through  a  vertex.
Figure  3  illustrates  the  complexity of scenes handled by Shirai's
program. The Binford-Horn system was intended to provide the base for
a system such as Shirai's by providing a partial line drawing without
special assumptions about the scene.  It  used  a  local  directional
edge operator and an optimal sequential decision process to group the
edge points into continuous curves.

It is interesting to compare these systems with biological ones.  The
directional  edge  operators  which  are  scanned  over the image are
analogous to  the  edge  detector  cells  discovered  by  Heubel  and
Wiesel[1968]  in  higher  animals.     In  practice, large brightness
gradients at reflections and  on  curved  surfaces  cause  masses  of
spurious  edge  fragments.     Smooth  gradients  are  eliminated  by
subtracting the local average at each point,  a  process  similar  to
lateral inhibition in the retina of animals.



		REAL WORLD VISION



The   blocks   world   illustrates  many  basic  aspects  of  machine
perception.   However, since many critical  problems  encountered  in
perceiving  real  world  scenes  do  not arise, few of the techniques
developed extend to this domain. For example:

1. Important problems in segmentation were avoided by using uniformly
painted  blocks.   Moreover, all boundaries were straight lines.  The
region-growing and edge-finding techniques developed in this  context
cannot  cope  with  the  textures  and  variations of brightness that
predominate in the real world.

2. The precise topological  descriptions  that  characterized  simple
polyhedra  are  inappropriate  or unobtainable for complex real world
objects such as trees.

3. Interpretation  by  exhaustively  matching  all  known  prototypes
against  each  segmented  body  is not feasible with large numbers of
objects and cluttered scenes.

Description of simple polyhedral scenes was  difficult  enough;  with
these  added  obstacles,  is there hope for success in perceiving the
real world?    Perception in  the  blocks  world  sought  a  complete
description  of  everything  present. It may not be possible (or even
meaningful)  to  obtain  exhaustive  descriptions  of  real   scenes.
However,  complete  descriptions  are  seldom  needed;  a  system  is
typically concerned with only a few objects required  to  complete  a
specific task.

For  blocks, we restricted our programs to black and white images and
distinguished structures of blocks solely on the basis of shape.   In
the  real  world, there is a tremendous redundancy of visual cues. We
can use color, texture, depth, size, and surface orientation, as well
as   shape,   whichever   distinguishes   a  particular  object  most
effectively.

Real world objects are usually found in well defined contexts;  e.g.,
telephones   are  expected  on  tables  but  not  in  waste  baskets.
Recognition of a few prominent  landmarks,  combined  with  a  priori
knowledge  of the environment can thus severely restrict what objects
may be present in each part of the scene. While these objects may  be
difficult   to  describe,  there  will  usually  be  sufficient  cues
available to discriminate easily amongst the  alternatives.    Often,
very gross descriptions of complex attributes like shape will suffice
to  discriminate  amongst  a  limited  number  of  grossly  different
alternatives  (e.g.,  a person can be distinguished from a dog simply
by the predominantly vertical orientation of a human body).

Real world vision can be viewed as a strategy problem: Given a  task,
first  decide  where  to look for objects of interest and then decide
how to distinguish  them  from  other  objects  that  might  also  be
present.   The system must limit interpretations to a small subset of
possible objects, selected on the basis of a priori expectations  and
crude  descriptions  of  the  scene.    Segmentation  can be based on
attributes which are known to be uniform over these objects. The  key
problems of information overload are overcome by tightly coordinating
segmentation and interpretation with world knowledge and task  goals.
The overload cannot be solved by merely building faster computers and
bigger memories; hardware improvements will aid  adequate  techniques
but do little for exhaustive techniques.

The  principle  work to date on real world vision has concentrated on
segmentation and representation.  Segmentation of textured scenes has
been  studies as a two-dimensional problem for agricultural and earth
resource survey applications.  Bajcsy  [1972]  has  analyzed  outdoor
scenes with perspective, where three-dimensional texture descriptions
are important.      Textures were described hierarchically  in  terms
of   simpler   texture  elements  and  their  spatial  relationships.
Descriptors for texture elements  and  relations  were  derived  from
Fourier  analysis.   Typical attributes were directionality (if any),
size, contrast, and spacing  of  texture  elements.      The  Fourier
transform  was  found troublesome,however, and color descriptors were
added to improve performance.  Some depth relations could be observed
from  texture  gradient.     An attempt was made to obtain consistent
interpretations by first confirming region boundaries by  independent
properties,  making  three-dimensional  interpretations, and matching
region descriptors with those of sky, trees, grass, etc.  in a  world
model.

The  quality  of  interpretation  was  limited  by  unreliability  of
region-growing processes. Further work in outdoor scenes attempts  to
incorporate  the  world  model  and  interpretation  into  the region
growing process. Regions are merged not only because of similarity of
properties, but because the consistency of semantic interpretation is
improved.


Typical  robot  tasks  such  as  manipulation,  collision  avoidance,
display and recognition  were  analyzed  to  determine  computational
primitives  required  for descriptions of shape.  Although some would
disagree, our criteria for shape representation are [Binford 1971]:

a) Representations should be symbolic at a high  level  in  order  to
interface with knowledge of the problem domain.

b)  Representations  should  depend on segmentation into parts, which
may have subparts.

c) Primitives should be three-dimensional volume descriptions, rather
than surface descriptions to allow a natural choice of parts.

d)  Descriptions  should  be  generative.     A  modest collection of
primitives should allow description of a vast set of objects.

We will outline one representation that fulfils these desiderata  for
a  large  class  of curved objects. Objects are described in terms of
components which are simple to describe,  and  the  relationships  of
these  parts.  A useful shape primitive for many curved objects is an
arbitrary space curve, and  normal  cross-sections  along  this  axis
(figure  4).      Snake-like  objects,  helices, toroids, and locally
helical and toroidal shapes are naturally described [Binford 71]. Our
basic  definition of a simple piece is that the direction of its axis
be continuous and that the cross-section function along that axis  be
continuous.    We  look  for large changes in the cross- section, and
consider them as likely places  for  segmenting  the  object.     The
segmentation  process must be flexible and able to generate alternate
propositions.   A higher level routine will  ultimately  select  from
the  alternatives.     Figure  5  shows  an  experimentally  obtained
computer description of a doll [Agin 72].
		INDUSTRIAL APPLICATIONS

Recently,  several  laboratories  have begun to apply techniques from
perception  research  to  practical  industrial  tasks.      Stanford
University  has  demonstrated simple assembly operations using vision
and touch. General Motors laboratories has succeeded  in  mounting  a
wheel  on  an axle. Stanford Research Institute and Hitachi Ltd. have
each demonstrated systems which can distinguish sheet metal parts  on
a  moving  conveyor  belt  and  determine their orientation to enable
manipulation.   Template  matching  techniques  were  used  to   take
advantage of the two dimensional nature of these tasks. Moreover, the
conveyor demonstrations relied on the contrast between shiny  metalic
parts  and  the  black belt to simplify segmentation. Many industrial
processes share similar constraints or can be readily  redesigned  to
do  so.  We thus expect a proliferation of industrial applications of
computer perception in the near future.